#include"myTree.h"
using namespace std;

myTrie::myTrie() {
	root =new TrieNode();
}
void myTrie::insert(string s) {
	if (s=="") {
		++root->end;
		return;
	}
	TrieNode* now = root;
	for (int i=0;i<s.length();++i) {
		if (now->nodes.find(s.at(i)) == now->nodes.end()) {
			now->nodes[s.at(i)] = new TrieNode();
		}
		++now->pass;
		now = now->nodes[s.at(i)];
	}
	++now->end;
}
int myTrie::search(string s) {
	if (s == "") {
		return root->end;
	}
	TrieNode* now = root;
	for (int i = 0; i < s.length(); ++i) {
		if (now->nodes.find(s.at(i)) == now->nodes.end()) {
			return 0;
		}
		now = now->nodes[s.at(i)];
	}
	return now->end;
}
int myTrie::prefixNum(string s){
	if (s=="") {
		return -1;
	}
	TrieNode* now = root;
	for (int i = 0; i < s.length(); ++i) {
		if (now->nodes.find(s.at(i)) == now->nodes.end()) {
			return 0;
		}
		now = now->nodes[s.at(i)];
	}
	return now->pass;
}
void myTrie::delete_str(string s,int count) {
	if (s=="") {
		root->end=(root->end>=count) ? root->end - count:0;
		return;
	}
	int en=search(s);
	if (en) {
		if (count < en) { en = count; }
		TrieNode* now = root;
		for (int i = 0; ; ++i) {
			if (i < s.length())
			{
				now->pass -= en;
			}
			else {
				now->end = 0;
				break;
			}
			if (now->pass==0) {
				_myTrie(now);
				now = nullptr;
				return;
			}
			now = now->nodes[s.at(i)];
		}
	}
}
void myTrie::_myTrie(TrieNode* proot) {
	if (!proot) {
		return;
	}
	if (proot->nodes.empty()) {
		delete proot;
		proot = nullptr;
		return;
	}
	for (pair<char,TrieNode*> x: proot->nodes) {
		_myTrie(x.second);
	}
	delete proot;
}
myTrie::~myTrie() {
	_myTrie(root);
}
void myTrie::get_pass_end_have(string s, int& pa, int& en, bool& ha) {
	int len = s.length();
	TrieNode* p = root;
	for (int i = 0; i < len; ++i) {
		if (p->nodes.find(s.at(i)) == p->nodes.end()) {
			ha = false;
			en = 0;
			pa = 0;
			return;
		}
		p = p->nodes[s.at(i)];
	}
	ha = true;
	pa = p->pass;
	en = p->end;
	return;
}